package leetcode_5000;

import java.util.ArrayList;
import java.util.List;

import helpclass.TreeNode;


/**
 *@author 周杨
 *SumOfRootToLeafBinaryNumbers_5017 问一棵树的二进制路径和
 *describe:递归
 *2019年4月7日 下午13:55
 */
public class SumOfRootToLeafBinaryNumbers_5017 {
	public static void main(String[] args) {
		SumOfRootToLeafBinaryNumbers_5017 test = new SumOfRootToLeafBinaryNumbers_5017();
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(0);
		root.right = new TreeNode(1);
		System.out.println(test.sumRootToLeaf(root));
		System.out.println(test.convert("0111"));
		
	}
	
	public int sumRootToLeaf(TreeNode root) {
		List<StringBuilder> res = help(root);
		double sum = 0;
		int MOD =1000000007;
		for(StringBuilder sb:res) {
			sum = (sum +convert(sb.toString()))%MOD;
		}
		return (int) sum;
    }
	
	public List<StringBuilder> help(TreeNode root) {
		List<StringBuilder> res = new ArrayList<StringBuilder>();
		if(root == null) {
			return null;
		}
		else {
			List<StringBuilder> left = help(root.left);
			List<StringBuilder> right = help(root.right);
			if(left != null) {
				for(StringBuilder sb:left) {
					sb.append(root.val);
					res.add(sb);
				}
			}
			if(right != null) {
				for(StringBuilder sb:right) {
					sb.append(root.val);
					res.add(sb);
				}
			}
			if(left == null && right == null) {//左右皆空
				StringBuilder sb = new StringBuilder();
				sb.append(root.val);
				res.add(sb);
			}
		}
		return res;
	}
	
	public int convert(String s) {
		int MOD =1000000007;
		double ans = 0;
		char[] chars = s.toCharArray();
		for(int i=0;i<chars.length;++i) {
			if(chars[i] == '1') {
				ans = ((ans+Math.pow(2,i)%MOD)%MOD);
			}
		}
		return (int) ans;
	}
	
	
	int mod = 1000000007;
    public int sumRootToLeaf1(TreeNode root) {
        return dfs(root, 0);
    }

    public int dfs(TreeNode root, int val) {
        if (root == null) return 0;
        val = (val * 2 + root.val) % mod;
        return (root.left == root.right ? val : dfs(root.left, val) + dfs(root.right, val)) % mod;
    }
	
}
